package org.hegang.algorithm.quicksort;


/**
 * @ClassName QuickSort
 * @Describe: 快速排序
 * @Author: gang.he
 * @Email: SmileSkylife@outlook.com
 * @Date: Created in 0:54 2019/6/29
 * @Modified By:
 * @Version V1.0
 */
public class QuickSort {
    /**
     * 快速排序
     *
     * @param quickSort
     * @param left
     * @param right
     */
    public void quickSort(int[] quickSort, int left, int right) {
        if (quickSort == null || quickSort.length == 0) {
            return;
        }
        //选取第一个数作为基准数，亦可按照一定规则选取,从右边开始分割
        int start = left;
        int end = right;
        int key = quickSort[left];

        while (start < end) {
            while (start < end && quickSort[end] >= key) {
                end--;
            }
            if (start < end) {
                quickSort[start] = quickSort[end];
                start++;
            }

            while (start < end && quickSort[start] <= key) {
                start++;
            }
            if (start < end) {
                quickSort[end] = quickSort[start];
                end--;
            }
        }
        //从始至终，变化的只有一个数，最后把基准值key赋值给它就行了
        quickSort[start] = key;
        if (start - 1 > left) {
            quickSort(quickSort, left, start - 1);
        }
        if (end + 1 < right) {
            quickSort(quickSort, end + 1, right);
        }
    }

    /**
     * 快速排序 [易于理解]
     *
     * @param quickSort
     * @param left
     * @param right
     */
    public void optimizationQuickSort(int[] quickSort, int left, int right) {
        int start = left;
        int end = right;
        while (start < end) {
            while (start < end && quickSort[start] <= quickSort[end]) {
                end--;
            }
            if (quickSort[start] > quickSort[end]) {
                int temp = quickSort[start];
                quickSort[start] = quickSort[end];
                quickSort[end] = temp;
                start++;
            }
            while (start < end && quickSort[end] >= quickSort[start]) {
                start++;
            }
            if (quickSort[end] < quickSort[start]) {
                int temp = quickSort[end];
                quickSort[end] = quickSort[start];
                quickSort[start] = temp;
                end--;
            }
        }
        if (left < start - 1) {
            optimizationQuickSort(quickSort, left, start - 1);
        }
        if (right > end + 1) {
            optimizationQuickSort(quickSort, end + 1, right);
        }
    }
}
